package cn.edu.jxau.test;

public class UnionFind {
    
    /**
     * 触点集
     */
    private int[] id;

    /**
     * 权重
     */
    private int[] weight;

    /**
     * 连通分量个数
     */
    private int count;

    public UnionFind(int count) {

        this.count = count;
        id = new int[count];
        weight = new int[count];
        for (int i = 0; i < id.length; i++) {
            id[i] = i;
            weight[i] = 1;
        }
    }

    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    public int count() {
        return count;
    }

    public int find(int p) {

        while (p != id[p]) {
            p = id[p];
        }
        return p;
    }

    public void union(int p, int q) {

        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ) { // 已等价
            return;
        }
        if (weight[rootP] < weight[rootQ]) { // 将连通分量rootP连到rootQ上
            id[rootP] = rootQ;
            weight[rootQ] += weight[rootP];
        } else {
            id[rootQ] = rootP;
            weight[rootP] += weight[rootQ];
        }
        count --;
    }
}
